Brief Background on Binary System:
In digital systems, unsigned numbers are represented in binary format. In binary format, a number is represented as a sequence of “1”s and/or “0”s. Since binary number system is a base 2 system (as compared to decimal system where the base is 10), each digit (called as bit) of the binary number, going from right to left, represents an increasing power of 2. The right most bit (referred as Least Significant Bit and abbreviated as LSB in this document) represents 20, the following bit represents 21 and so on. The left most bits is referred as Most Significant Bit. In this document, binary numbers will be represented with N′b prefix. For example 3′b011 represents a binary number which has three bits and these bits are 0, 1 and 1 (reading from left to right). Likewise in this document numbers with N′d prefix indicates that a decimal number is represented in N bit binary form. For example 4′d9, indicates decimal 9 represented in 4-bit binary form.
To find the decimal equivalent of a number represented in binary format, we have to just compute the sum of the product of the bit and the power of 2 that the particular bit position represents. Two examples of converting binary number to decimal equivalent are given below3′b101=1×22+0×21+1×20=5 (in decimal)5′b10010=1×24+0×23+0×22+1×21+0×20=18 (in decimal)
Since the binary format is a base 2 system, quotient and remainder resulting by a division of the number by power of 2 is inherently embedded in the number. For example, the remainder resulting from division of an N-bit number by 8 (23) is obtained by simply separating the least significant 3 bits from the rest the number. The quotient of this division would be the most significant ‘N−3’ bits. In this document, we use the following notations for quotient and remainder:    qd—Quotient of division of an unsigned number by divisor d.    rd—Reminder of division of an unsigned number by divisor d.
FIG. 1 shows the quotient and remainder when an N-bit unsigned number is divided by a divisor which is a power of 2 (d=2,4,8,16,32,64 . . . etc.), i.e. FIG. 1 illustrates quotients (qd) and remainders (rd) resulting from division of an N-bit number by a power of 2(d=2,4,8,16,32,64).
Modulo 9 and Modulo 7 on Unsigned Numbers:
Modulo operation is the process of finding the remainder of a division operation. The result of the modulo operation is often termed “modulo X”. Therefore ‘modulo X’ represents the remainder when a number is divided by “X”.
In this document, ‘modulo 9’ represents remainder when an unsigned number is divided by 9. Similarly ‘modulo 7’ represents remainder when an unsigned number is divided by 7.
Modulo Operation:
In digital circuits, modulo operation, where divisor is a power of 2, is straight forward and is done by simply picking out the relevant number of lower bits as depicted in FIG. 1. However since 9 and 7 are not powers of 2, the modulo9 and modulo7 operation is not simple and straight forward and results in extensive and often complex digital logic implementations. Moreover, separate logic circuits are commonly required for modulo9 and modulo7 calculations.
It is a challenge for designers of logic circuits to design a simple and scalable scheme and implementation for calculating modulo9 and modulo7 on unsigned binary numbers.